package sequential_apriori;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SequentialApriori {

	// Object variables
	private double minSupport;
	private int windowSize;

	public SequentialApriori(double minSupport, int windowSize) {
		this.minSupport = minSupport;
		this.windowSize = windowSize;
	}

	/* Execute the sequential apriori algorithm for the object data */
	public int runApriori(String data) {
	
		// Initialize the sequence counter
		int k = 1;

		// Initialize the frequent-sequence array list
		ArrayList F = new ArrayList();
		String[] dummyArray = {"dummy"};
		F.ensureCapacity(k);
		F.add(0, dummyArray);

		// Get candidate 1-subsequences and their supports
		Object[] oneSubSeqData = getOneSubsequences(data);

		// Initialize the candidate subsequences and support count arrays
		String[] one_k = (String[])oneSubSeqData[0];
		Integer[] one_k_supports = (Integer[])oneSubSeqData[1];

		int i;
		/* DEBUGGING: Show the 1-subsequences and their support counts
		for(i=0; i<one_k.length; i++) {
			System.out.println("Candidate subsequence '" + one_k[i] + "' has support: " + one_k_supports[i]);
		}
		System.out.println(); */

		// Get frequent 1-subsequences and supports
		int numDataLines = data.split("\n").length;
		System.out.println("numDataLines: " + numDataLines);
		Object[] freqSubSeqData = getFrequentSubsequences(k, one_k, one_k_supports, numDataLines);
		F.add(k, (String[])freqSubSeqData[0]);
		Double[] freqSupports = (Double[])freqSubSeqData[1];
	
		// DEBUGGING: Show the frequent 1-subsequences and their supports (%)
		for(i=0; i<freqSupports.length; i++) {
			System.out.println("Frequent subsequence '" + ((String[])F.get(1))[i] + "' has support: " + freqSupports[i]);
		}
		System.out.println();
		
		// Iterate until there are no new frequent k-subsequences
		while(((String[])F.get(k)).length>0) {

			// Increment k
			k++;
			
			// Generate candidate k-subsequences from the k-1 frequent subsequences
			String[] C_k = getCandidateSubsequences(k, (String[])F.get(k-1));

			if(C_k.length<1 || C_k[0]==null) {
				break;
			}

			// Find the support counts for each candidate k-subsequence
			Integer[] C_k_supports = getSupportCounts(C_k, data, this.windowSize);

			// DEBUGGING: Show the candidate subsequences and support count arrays
			for(i=0; i<C_k_supports.length; i++) {
				System.out.println("Candidate subsequence '" + C_k[i] + "' has support: " + C_k_supports[i]);
			}
			System.out.println();

			// Use the candidate support counts to get the frequent k-subsequences
			freqSubSeqData = getFrequentSubsequences(k, C_k, C_k_supports, numDataLines);
			F.add(k, (String[])freqSubSeqData[0]);
			freqSupports = (Double[])freqSubSeqData[1];

			// DEBUGGING: Show the frequent k-subsequences and their supports (%)
			for(i=0; i<freqSupports.length; i++) {
				System.out.println("Frequent subsequence '" + ((String[])F.get(k))[i] + "' has support: " + freqSupports[i]);
			}
			System.out.println();
		}
		return 0;
	}

	/* Get the initial (ie. k=1) subsequences from the data and return the support counts for each one-subsequence */
	private Object[] getOneSubsequences(String dataLines) {

		// Initialize a return object which will contain both the candidate 1-subsequences and their supports
		Object[] data = new Object[2];

		// Initialize candidate and support ArrayLists
		ArrayList candidateList = new ArrayList();
		ArrayList supportList = new ArrayList();

		// Tokenize the data lines
		StringTokenizer dataTok = new StringTokenizer(dataLines);
		
		// Iterate until no tokens remain
		int listSize = 0;
		while(dataTok.hasMoreTokens()) {

			// Get the next token and obtain it's index value w.r.t. the candidateList
			String token = dataTok.nextToken();
			int tokenIndex = candidateList.indexOf(token);
			
			if(tokenIndex == -1) {
				// If the token doesn't exist in the candidates (ie. index==-1) increment list size and add it
				candidateList.ensureCapacity(listSize+1);
				candidateList.add(listSize, token);
				supportList.ensureCapacity(listSize+1);
				supportList.add(listSize, 1);
				listSize++;
		} else {
				// If the token does exist in the candidates (ie. index>-1) increment the support count for that candidate (but don't increment listSize)
				Integer prevSupport = (Integer)supportList.get(tokenIndex);
				supportList.set(tokenIndex, prevSupport+1);
			}
		}

		// Convert from ArrayLists to Arrays
		String[] candidateOneSubsequences = new String[candidateList.size()];
		Integer[] candidateSupports = new Integer[supportList.size()];
		candidateList.toArray(candidateOneSubsequences);
		supportList.toArray(candidateSupports);

		// Store the data arrays in the return object and return
		data[0] = candidateOneSubsequences;
		data[1] = candidateSupports;
		return data;
	}

	/* Use the candidate subsequences, support counts, and minSupport to determine the frequent k-subsequences */
	private Object[] getFrequentSubsequences(int k, String[] candidates, Integer[] supports, int numDataLines) {

		// Initialize a return object which will contain the frequent k-subsequences and their supports
		Object[] freqData = new Object[2];

		// Initialize frequent and support arraylists
		ArrayList frequentList = new ArrayList();
		ArrayList supportList = new ArrayList();
		int listSize = 0;
		Double candidateSupport;

		for(int i=0; i<candidates.length; i++) {
			// Find the support percentage for this candidate sequence
			candidateSupport = (double)supports[i]/(double)numDataLines;
			if(candidateSupport>this.minSupport) {
				// If support is greater than the minimum threshold, update the frequent and support lists
				frequentList.ensureCapacity(listSize+1);
				frequentList.add(listSize, candidates[i]);
				supportList.ensureCapacity(listSize+1);
				supportList.add(listSize, candidateSupport);
				listSize++;
			}
		}

		// Convert from ArrayLists to Arrays
		String[] frequentSubsequences = new String[frequentList.size()];
		Double[] frequentSupports = new Double[supportList.size()];
		frequentList.toArray(frequentSubsequences);
		supportList.toArray(frequentSupports);
		
		//. Store the data arrays in the return object and return
		freqData[0] = frequentSubsequences;
		freqData[1] = frequentSupports;
		return freqData;
	}

	/* Use the k-1 frequent-subsequences to generate the candidate k-subsequences */
	private String[] getCandidateSubsequences(int k, String[] prevFreq) {

		ArrayList candidateSubsequences = new ArrayList();
		int candidateIndex = 0;

		// Generate candidates by combining previous frequent subsequences which overlap by their middle elements
		for(int i=0; i<prevFreq.length; i++) {
			for(int j=0; j<prevFreq.length; j++) {

				// Initialize sequence arrays and string holders
				String[] seq1 = prevFreq[i].split(" ");
				String[] seq2 = prevFreq[j].split(" ");
				String a = "";
				String b = "";

				if(seq1.length==1) {
					// For 1-subsequences, simply concatenate each pair
					candidateSubsequences.add(candidateIndex, prevFreq[i] + " " + prevFreq[j]);
					candidateIndex++;
				} else {

					// Remove the first element of sequence 1 and the last element of sequence 2
					String[] modSeq1 = new String[seq1.length-1];
					modSeq1 = Arrays.copyOfRange(seq1, 1, seq1.length);
					String[] modSeq2 = new String[seq2.length-1];
					modSeq2 = Arrays.copyOfRange(seq2, 0, seq2.length-1);
					
					// Generate the strings from these shortened sequences
					for(int l=0; l<modSeq1.length; l++) {
						a += seq1[l+1] + " ";
						b += seq2[l] + " ";
					}

					// If the two shortened sequences are equal, store this as a candidate and increment the index
					if(a.equals(b)) {
						candidateSubsequences.add(candidateIndex, prevFreq[i] + " " + seq2[seq2.length-1]);
						candidateIndex++;
					}
				}
			}
		}

		// Convert from ArrayList to Array
		String[] candidateArray = new String[candidateSubsequences.size()];
		candidateSubsequences.toArray(candidateArray);

		return candidateArray;
	}

	/* Find the support counts of each candidate subsequence using the specified window size */
	private Integer[] getSupportCounts(String[] candidates, String dataLines, int windowSize) {

		Integer[] supports = new Integer[candidates.length];
		int kVal = candidates[0].replaceAll("^\\s+", "").split("\\s+").length - 1;
		int realWinSize = Math.max(windowSize-1, kVal);
		String[] window = new String[realWinSize];

		String[] lineArray = dataLines.split("\n");

		for(int i=0; i<candidates.length; i++) {
			
			// Get the candidate subsequence
			String[] candidateTokens = candidates[i].replaceAll("^\\s+", "").split("\\s+");

			// Initialize the support counter for this candidate
			supports[i] = 0;

			// Count the number of times it occurs in the data using the windowSize to account for gaps
			for(int j=0; j<lineArray.length; j++) {
				
				String[] lineTokens = lineArray[j].replaceAll("^\\s+", "").split("\\s+");
				for(int k=0; k<lineTokens.length; k++) {
					
					if(lineTokens[k].equals(candidateTokens[0])) {
						
						// Once the first element is found, create the window in front of it and check for the sequence
						window = Arrays.copyOfRange(lineTokens, k+1, k+windowSize);
						int sequenceCounter = 1;
						for(int l=0; l<window.length; l++) {
							
							// If another element in the sequence is found, increment the counter
							if(window[l]!=null && window[l].equals(candidateTokens[sequenceCounter])) {
								sequenceCounter++;
								
								// If the sequence counter reaches the length of the sequence, the sequence is found. Increment support.
								if(sequenceCounter==candidateTokens.length) {
									supports[i]++;
									break;
								}
							}
						}
					}
				}
			}
		}

		return supports;

	}

}
